package com.hanxiaozhang.no10leetcode.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给一个含有不同整数的数组集合，返回所有的排列组合
 * 实例:
 * 输出: [1,2,3]
 * 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
 * 整体思路（灵魂）：
 * --数组中，各个位置交换。
 * --结束条件，需要交换的元素到最后一个位置。
 * <p>
 * 具体步骤：
 * 构建一个递归方法：
 * -- 递归入参：需要技巧
 * --- start  开始交互元素位置
 * --- nums   数组
 * --- result 结果集
 * -- 逻辑：
 * --- 边界条件：start ==  nums.length 时，加入结果
 * --- 循环：开始条件：start，结束条件：i <  nums.length
 * ---- 每次循环 i. start 与 i 交互；ii. 调用 backTrack(start + 1 ..； iii.start 与 i 交互（恢复现场）
 *
 * @author hanxinghua
 * @create 2024/2/2
 * @since 1.0.0
 */
public class No46Permutations {


    public static void main(String[] args) {
        int[] nums = {1, 2, 3};

        System.out.println(permute(nums));

    }


    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        backTrack(0, nums, result);
        return result;
    }

    /**
     * @param start  开始交互元素位置
     * @param nums   数组
     * @param result 结果集
     */
    private static void backTrack(int start, int[] nums, List<List<Integer>> result) {

        if (start == nums.length) {
            List<Integer> list = new ArrayList<>();
            for (Integer i : nums) {
                list.add(i);
            }
            result.add(list);
        }

        for (int i = start; i < nums.length; i++) {
            // 交互位置
            swap(nums, start, i);
            // 开始位置后移一位
            backTrack(start + 1, nums, result);
            // 恢复现场
            swap(nums, start, i);
        }
    }


    /**
     * 交换
     *
     * @param nums
     * @param start
     * @param i
     */
    private static void swap(int[] nums, int start, int i) {
        if (start == i) {
            return;
        }

        int temp = nums[start];
        nums[start] = nums[i];
        nums[i] = temp;
    }

}
